#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/*
  平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：
  它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
  平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树等。

  平衡二叉树是在二叉排序树(BST)上引入的，就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降，
  那么AVL就保持住了(BST)的最好时间复杂度O(logn)，所以每次的插入和删除都要确保二叉树的平衡。

 */

#define MAXSIZE 512

typedef struct obj_n_t
{
  int obj_key;
}obj_node_t;

typedef struct tree_n_t
{
  int key;
  struct tree_n_t * left, * right;
  int height;
}tree_node_t;

tree_node_t * stack[MAXSIZE]; // warning! the tree can contain 256 leaves at most!
int i = 0;

void stack_clear()
{
  while (i != 0) {
    stack[i-1] = NULL;
    i--;
  }
}

int stack_empty()
{
  return (i == 0);
}

int push(tree_node_t * node)
{
  if (i < MAXSIZE) {
    stack[i++] = node;
    return 0;
  }
  else
    return -1;
}

tree_node_t * pop()
{
  if (i > 0)
    return stack[--i];
  else
    return NULL;
}

tree_node_t * get_node()
{
  tree_node_t * des;

  des = (tree_node_t *) malloc (sizeof(tree_node_t));
  return des;
}

void return_node(tree_node_t * src)
{
  free(src);
}

// 建立左旋转函数
void left_rotation(tree_node_t * node)
{
  tree_node_t * src;
  int key;

  src = node->left;
  key = node->key;
  node->left = node->right;
  node->key = node->right->key;
  node->right = node->left->right;
  node->left->right = node->left->left;
  node->left->left = src;
  node->left->key = key;
}

// 建立右旋转函数
void right_rotation(tree_node_t * node)
{
  tree_node_t * src;
  int key;
  
  src = node->right;
  key = node->key;
  node->right = node->left;
  node->key = node->left->key;
  node->left = node->right->left;
  node->right->left = node->right->right;
  node->right->right = src;
  node->right->key = key;
}

int rebalance(tree_node_t * node)
{
  int finished = 0;
  int height, old_height;

  while (!stack_empty() && !finished) {
    node = pop(); // back to the root along the search path.
    old_height = node->height;

    if (node->left->height - node->right->height == 2) {
      if (node->left->left->height - node->right->height == 1) {
	right_rotation(node);
	node->right->height = node->right->left->height + 1;
	node->height = node->right->height + 1;
      }
      else {
	left_rotation(node->left);
	right_rotation(node);
	height = node->left->left->height;
	node->left->height = height + 1;
	node->right->height = height + 1;
	node->height = height + 2;
      }
    }
    else if (node->left->height - node->right->height == -2) {
      if (node->right->right->height - node->left->height == 1) {
	left_rotation(node);
	node->left->height = node->left->right->height + 1;
	node->height = node->left->height + 1;
      }
      else {
	right_rotation(node->right);
	left_rotation(node);
	height = node->right->right->height;
	node->left->height = height + 1;
	node->right->height + height + 1;
	node->height = height + 2;
      }
    }
    else {
      if (node->left->height > node->right->height)
	node->height = node->left->height + 1;
      else
	node->height = node->right->height + 1;
    }
    
    if (node->height == old_height)
      finished = 1;
  }

  stack_clear();

  return 0;
}

tree_node_t * creat_tree()
{
  tree_node_t * root;

  root = get_node();
  root->left = root->right = NULL;
  root->height = 0;

  return root; // build up an empty tree. the first insert bases on the empty tree.
}

obj_node_t * find(tree_node_t * tree, int query_key)
{
  tree_node_t * src;

  if (tree->left == NULL)
    return NULL;
  else {
    src = tree;
    while (src->right != NULL) {
      if (query_key < src->key)
	src = src->left;
      else
	src = src->right;
    }
    
    if (src->key == query_key)
      return (obj_node_t *) src->left;
    else
      return NULL;
  }
}

int insert(tree_node_t * tree, obj_node_t * new_obj)
{
  tree_node_t * src;
  int query_key, new_key;
  tree_node_t * old_leaf, * new_leaf;

  query_key = new_key = new_obj->obj_key;
  if (tree->left == NULL) {
    tree->left = (tree_node_t *) new_obj;
    tree->key = new_key;
    tree->height = 0;
    tree->right = NULL;
  }
  else {
    stack_clear();
    src = tree;
    while (src->right != NULL) {
      // use stack to remember the path from root to the position at which the new object should be inserted.
      // then after inserting, we can rebalance ffrom the parrent node of the leaf which pointing to new object to the root node.
      push(src);
      if (query_key < src->key)
	src = src->left;
      else
	src = src->right;
    }
    if (src->key == query_key)
      return -1;
    else {
      // It must allocate 2 node space in memory.
      // One for the new one, another for the old one.
      // the previous node becomes the parrent of the new node.
      // when we delete a leaf, it will free two node memory spaces as well.
      old_leaf = get_node();
      old_leaf->left = src->left;
      old_leaf->key = src->key;
      old_leaf->right = NULL;
      old_leaf->height = 0;
      
      new_leaf = get_node();
      new_leaf->left = (tree_node_t *) new_obj;
      new_leaf->key = new_key;
      new_leaf->right = NULL;
      new_leaf->height = 0;

      if (src->key < new_key) {
	src->left = old_leaf;
	src->right = new_leaf;
	src->key = new_key;
      }
      else {
	src->left = new_leaf;
	src->right = old_leaf;
      }

      src->height = 1;
    }
  }

  rebalance(src);

  return 0;
}

int del(tree_node_t * tree, int key)
{
  tree_node_t * src, * upper, * other;

  if (tree->left == NULL)
    return -1;
  else if (tree->right == NULL) {
    if (tree->key == key) {
      tree->left = NULL;
      return 0;
    }
    else
      return -1;
  }
  else {
    src = tree;
    stack_clear();

    while (src->right != NULL) {
      upper = src;
      push(upper);
      
      if (key < src->key) {
	src = upper->left;
	other = upper->right;
      }
      else {
	src = upper->right;
	other = upper->left;
      }
    }

    if (src->key != key)
      return -1;
    else {
      upper->key = other->key;
      upper->left = other->left;
      upper->right = other->right;
      upper->height = upper->height - 1;
      return_node(src);
      return_node(other);
      rebalance(pop());

      // here must pop, then rebalance can run from the parrent of upper, because upper has become a leaf.
      return 0;
    }
  }
}

int travel(tree_node_t * tree)
{
  stack_clear();

  if (tree->left == NULL) 
    push(tree);
  else if (tree->left != NULL) {
    int m = 0;
    push(tree);

    while (i != m) {
      if (stack[m]->left != NULL && stack[m]->right != NULL) {
	push(stack[m]->left);
	push(stack[m]->right);
      }
      m++;
    }
  }

  return 0;
}

int test_structure(tree_node_t * tree)
{
  int state = -1;
  
  travel(tree);
  while (!stack_empty()) {
    --i;
    if (stack[i]->right == NULL && stack[i]->height == 0) // this statement is leaf, but also contains an empty tree.
      state = 0;
    else if (stack[i]->left != NULL && stack[i]->right != NULL) {
      if (abs(stack[i]->height - stack[i]->height) <= 1)
	state = 0;
      else {
	state = -1;
	stack_clear();
      }
    }
  }

  stack_clear();

  return state;
}

int remove_tree(tree_node_t * tree)
{
  travel(tree);
  if (stack_empty())
    return -1;
  else {
    while (!stack_empty())
      return_node(pop());
    return 0;
  }
}

void help()
{
  char *p[] = {"1. Create a tree\n",
	       "2. insert a int type object\n",
	       "3. Test the structure of the tree\n",
	       "4. find a object\n",
	       "5. travel tree\n", 
               "6. Delete a object\n",
	       "7. remove the tree\n",
	       "0. exit\n",
	       "please select:"};
  int i ;

  for (i = 0; i < 9; i++)
    printf("%s", p[i]);
}

int main()
{
  tree_node_t * atree = NULL;
  obj_node_t obj[256], * f;  // MAXSIZE = n (number of leaf) + (n - 1) number of node.
  int n, j = 0;
  int item = -1, count;

  printf("Now Let's start this program! There is no tree in memory.\n");
  while (item != 0) {
    printf("Root address = %p\n",atree);
    help();
    scanf("%d", &item);

    switch(item) {
    case 1:
      atree = creat_tree();
      printf("A new empty tree has been built up.\n");
      break;
    case 2:
      if (atree != NULL) {
	while ( n != 3458) {
	  printf("please insert a new object.\nonly one object every time (3458 is an end code) : ");
	  scanf("%d", &n);
	  if (n != 3458) {
	    obj[j].obj_key = n;
	    if (insert(atree, &obj[j]) == 0) {
	      j++;
	      printf("Integer %d has been input.\n", n);
	    }
	    else
	      printf("Insert failed.\n\n");
	  }
	}
      }
      else
	printf("No tree in memory, insert faile.\n");
      break;
      
    case 3:
      if (atree != NULL) {
	n = test_structure(atree);
	if (n == -1)
	  printf("It's not a correct AVL tree.\n");
	if (n == 0)
	  printf("It's a AVL tree\n");
      }
      else
	printf("No tree in memory, Test fail.\n");
      break;

    case 4:
      if (atree != NULL) {
	printf("What do you want to find : ");
	scanf("%d", &n);
	f = find(atree, n);

	if (f == NULL)
	  printf("Sorry, can't be found.\n");
	else
	  printf("object %d has been found.\n", f->obj_key);
      }
      else
	printf("No tree in memory, find fail.\n");
      break;

    case 5:
      if (atree != NULL) {
	travel(atree);
	for (count = 0; count < i; count++) 
	  printf("key : %d\n", stack[count]->key);
      }
      else
	printf("No tree in memory, travel fail.\n");
      break;
	
    case 6:
      if (atree != NULL) {
	printf("which object do you want to delete?\n");
	scanf("%d", &n);
	if (del(atree, n) == 0)
	  printf("%d has been deleted.\n");
	else
	  printf("No this object\n");
      }
      else
	printf("No tree in memory, delete fail.\n");
      break;

    case 7:
      if (atree != NULL) {
	remove_tree(atree);
	printf("the tree has been removed.\n");
	atree = NULL;
      }
      else 
	printf("No tree in memory, removing fail.\n");
      break;

    case 0:
      printf("program exit\n");
      exit(0);
       
    default:
      printf("No this operation.\n");
    }
    
    n = 0;
  }
}
